package 题目集.动态规划;

import org.junit.Test;

/**
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 * https://leetcode.cn/problems/edit-distance/description/
 * 注意：这里对链接的题目进行了改版，加了插入，删除，替换的代价。
 */
public class 编辑距离 {
    /**
     * 问题：word1[0~n]转换成word2[0~m]所使用的最少操作数
     * 这个题目可以拆分得到的集合有：
     *     1.最后往w1[i]插入一个字符。
     *     2.最后往w1[i]删除一个字符。
     *     3.最后往w2[j]插入一个字符。
     *     4.最后往w2[j]删除一个字符。
     *     5.替换w1[i]最后一个字符。
     *     6.替换w2[i]最后一个字符。
     *     7.不需要处理i和j的最后一个字符。
     *
     * 分析这些集合的选择条件
     *     集合1只有在j>0才可以选，（集合3同理）。
     *     集合2只有在i>0才可以选，（集合4同理）。
     *     集合5只有在i>0且j>0才可以选，集合6同理。
     *     集合7只有在i>0且j>0且w[i]==w[j]才可以选。
     * 分析这些集合哪些是重合的，去掉重合的集合，剩下的集合就是我们要求的集合。
     *     其中集合5和集合6是重合的，因为替换操作是对称的，所以只需要保留一个即可。
     * 分析大集合和小集合的关系：
     *     大集合是从这些集合中选择一个最小值。
     * 最后写出状态转移方程：
     *     w1[i]==w2[j]时，dp[i][j]=dp[i-1][j-1]
     *     w1[i]!=w2[j]时，dp[i][j]取下面五个集合中的较小值：
     *         1.对w1[i]插入操作：if(j>0) dp[i][j-1]+增加的代价
     *         2.对w1[i]删除操作：if(i>0) dp[i-1][j]+删除的代价
     *         3.对w2[j]插入操作：if(i>0) dp[i-1][j]+增加的代价
     *         4.对w2[j]删除操作：if(j>0) dp[i][j-1]+增加的代价
     *         5.替换操作：if(i>0&&j>0) dp[i-1][j-1]+替换的代价
     * 分析状态转移方程的边界条件，和转移方程的依赖顺序：
     *     dp[0][0]=0
     *     dp[0][j]=Math.min(j*增加的代价,j*删除的代价)
     *     dp[i][0]=Math.min(i*增加的代价,i*删除的代价)
     *     n，m一直依赖到1。所以应该从1递推到n，m。
     */
    public int minDistance(String word1, String word2) {
        w1 = word1.toCharArray();
        w2 = word2.toCharArray();
//        dp = new int[w1.length + 1][w2.length + 1];
//        for (int[] ints : dp) {
//            Arrays.fill(ints, -1);
//        }
//        return dfs(w1.length, w2.length);
        return dpFun2(w1.length, w2.length);
    }

    char[] w1;
    char[] w2;
    static final int ADD = 5, DEL = 1, EDIT = 1000;    //插入，删除，替换的代价
    int[][] dp;

    public int dfs(int i, int j) {
        if (dp[i][j] != -1) return dp[i][j];
        if (i == 0 || j == 0) {
            return Math.min(i * ADD, i * DEL) + Math.min(j * ADD, j * DEL);   //有一个为空串，则返回全部插入或删除中代价较小的一个
        }
        if (w1[i - 1] == w2[j - 1]) {
            dp[i][j] = dfs(i - 1, j - 1);
        } else {
            int add1 = dfs(i, j - 1) + ADD;  //往w1[i]插入一个字符
            int del1 = dfs(i - 1, j) + DEL;  //删除w1[i]字符

            int add2 = dfs(i - 1, j) + ADD;  //往w2[i]插入一个字符
            int del2 = dfs(i, j - 1) + DEL;  //删除w2[i]字符

            int edit = dfs(i - 1, j - 1) + EDIT;    //替换w[i]字符
            dp[i][j] = Math.min(add1, Math.min(del1, edit));
            dp[i][j] = Math.min(add2, Math.min(del2, dp[i][j]));
        }
        return dp[i][j];
    }

    public int dpFun(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.min(i * DEL, i * ADD);
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = Math.min(i * DEL, i * ADD);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (w1[i - 1] == w2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int add1 = dp[i][j - 1] + ADD;  //往w1[i]插入一个字符
                    int del1 = dp[i - 1][j] + DEL;  //删除w1[i]字符

                    int add2 = dp[i - 1][j] + ADD;  //往w2[i]插入一个字符
                    int del2 = dp[i][j - 1] + DEL;  //删除w2[i]字符

                    int edit = dp[i - 1][j - 1] + EDIT;    //替换w[i]字符
                    dp[i][j] = Math.min(add1, Math.min(del1, edit));
                    dp[i][j] = Math.min(add2, Math.min(del2, dp[i][j]));
                }
            }
        }
        return dp[n][m];
    }
    public int dpFun2(int n, int m){
        int[] dp = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            dp[i] = Math.min(i * DEL, i * ADD);
        }
        for (int i = 1; i <= n; i++) {
            int leftDown = dp[0];
            dp[0]=Math.min(i*DEL,i*ADD);
            for (int j = 1; j <= m; j++) {
                int old = dp[j];
                if (w1[i - 1] == w2[j - 1]) {
                    dp[j] = leftDown;
                } else {
                    int add1 = dp[j - 1] + ADD;  //往w1[i]插入一个字符
                    int del1 = dp[j] + DEL;  //删除w1[i]字符

                    int add2 = dp[j] + ADD;  //往w2[i]插入一个字符
                    int del2 = dp[j - 1] + DEL;  //删除w2[i]字符

                    int edit = leftDown + EDIT;    //替换w[i]字符
                    dp[j] = Math.min(add1, Math.min(del1, edit));
                    dp[j] = Math.min(add2, Math.min(del2, dp[j]));
                }
                leftDown = old;
            }
        }
        return dp[m];
    }

    @Test
    public void test() {
        System.out.println(minDistance("abcddd", "abe"));
    }
}
